Question 7.2
Using the 20 years of daily high temperature data for Atlanta (July through October) from Question 6.2 (file temps.txt), build and use an exponential smoothing model to help make a judgment of whether the unofficial end of summer has gotten later over the 20 years. (Part of the point of this assignment is for you to think about how you might use exponential smoothing to answer this question. Feel free to combine it with other models if you’d like to. There’s certainly more than one reasonable approach.) Note: in R, you can use either HoltWinters (simpler to use) or the smooth package’s es function (harder to use, but more general). If you use es, the Holt-Winters model uses model=”AAM” in the function call (the first and second constants are used “A”dditively, and the third (seasonality) is used “M”ultiplicatively; the documentation doesn’t make that clear).
While trying to exponentially smooth the data, we will need to first get an idea of an optimal alpha and beta parameter for the HoltWinters function. Let’s plot the data for 1996 and experiment with every combination of alpha from 0.2 to 0.5 and beta from 0.0 to 0.5
library(TTR)
temps <- read.table('temps.txt', header = TRUE, stringsAsFactors = FALSE)
#temps$DAY <- format(as.Date(temps$DAY, format = '%d-%b'), '%d-%b')
days <- temps$DAY
temps <- t(temps[,2:ncol(temps)])
colnames(temps) <- days
rownames(temps) <- 1996:2015
temps_ts <- ts(temps, start = 1996, frequency=1)
for(i in seq(from = 0.2, to = 0.5, by = 0.1)){
for(j in seq(from = 0.00, to = 0.5, by = 0.1)){
cat('Alpha: ',i, 'Beta: ', j,'\n')
temp_h <- HoltWinters(temps_ts[1,],alpha=i, beta = j, gamma = FALSE)
plot(temp_h)
}
}
Alpha: 0.2 Beta: 0
Alpha: 0.2 Beta: 0.1

Alpha: 0.2 Beta: 0.2

Alpha: 0.2 Beta: 0.3

Alpha: 0.2 Beta: 0.4

Alpha: 0.2 Beta: 0.5

Alpha: 0.3 Beta: 0

Alpha: 0.3 Beta: 0.1

Alpha: 0.3 Beta: 0.2

Alpha: 0.3 Beta: 0.3

Alpha: 0.3 Beta: 0.4

Alpha: 0.3 Beta: 0.5

Alpha: 0.4 Beta: 0

Alpha: 0.4 Beta: 0.1

Alpha: 0.4 Beta: 0.2

Alpha: 0.4 Beta: 0.3

Alpha: 0.4 Beta: 0.4

Alpha: 0.4 Beta: 0.5

Alpha: 0.5 Beta: 0

Alpha: 0.5 Beta: 0.1

Alpha: 0.5 Beta: 0.2

Alpha: 0.5 Beta: 0.3

Alpha: 0.5 Beta: 0.4

Alpha: 0.5 Beta: 0.5


An alpha value of 0.2 and beta of 0.2 seems to best smooth the data without losing any major characterstic changes. It also doesn’t appear to amplify any characteristic changes. Let’s Attempt a CUMSUM algorithm on the 1996 data with a 0.2 alpha and beta.
temp_h <- HoltWinters(temps_ts[1,],alpha=0.2, beta = 0.2, gamma = FALSE)
forecast <- temp_h$fitted[,1]
avg = mean(forecast)
s = forecast[1]
C = 1
threshold = -30
for(i in seq(from = 2, to = length(forecast))){
s = s + (forecast[i] - avg + C)
s = min(0, s)
if (s < threshold){
day_change = days[i]
day_index = i
break
}
}
print(day_change)
[1] "29-Sep"
xp = as.Date(strptime(days, format = '%d-%b'))
max = length(xp) - 1
xp = xp[2:max]
plot(x = xp, y = forecast, xlab = 'Dates', ylab='Temperatures', main='Atlanta Temperatures in 1996')
points(x = xp[day_index], y= forecast[day_index], col = 'red')
abline(h = avg)

The smoothing appears to have helped characterize the event change of summer to fall at Sept 29th. Before that date, the temperature did spike up to just below the average temperature, but never quite made it past. It then fell back down to which it never returned higher than the average temperature. As a quality check, let’s see if the average temperature is the right value to use. If the data has a lot of outliers or is greatly skewed left or right, then this will erroneously pull the mean away from the true center of that data. If that is the case, then the median temperature of the data is the more appropriate metric to use
hist(temps_ts[1,], main = '1996 Atlanta Temperatures', xlab = 'Temps')

The data is greatly left skewed. Let’s rerun the analysis again, but using the median instead of the mean in the CUSUM algorithm
temp_h <- HoltWinters(temps_ts[1,],alpha=0.2, beta = 0.2, gamma = FALSE)
forecast <- temp_h$fitted[,1]
median = median(forecast)
s = forecast[1]
C = 1
threshold = -30
for(i in seq(from = 2, to = length(forecast))){
s = s + (forecast[i] - median + C)
s = min(0, s)
if (s < threshold){
day_change = days[i]
day_index = i
break
}
}
print(day_change)
[1] "21-Sep"
plot(x = xp, y = forecast, xlab = 'Dates', ylab='Temperatures', main='Atlanta Temperatures in 1996 Using Median Temperature')
points(x = xp[day_index], y= forecast[day_index], col = 'red')
abline(h = median)

One can argue that the median was a better metric to use. The CUMSUM found the appropriate point at which the event change dropped below the data’s median value sooner than the mean metric did. Although the temperature slightly increased from that point, it never crossed the median line again for the rest of the year. Let’s use this analysis to guide the rest of our investigation on the remaining years of data.
weather_change_index = rep(0, 20)
for (i in seq(1,20)){
temp_h <- HoltWinters(temps_ts[i,],alpha=0.2, beta = 0.2, gamma = FALSE)
x <- temp_h$fitted[,1]
median = median(x)
C = 1
threshold = -30
s = x[1] - median + C
for(j in seq(from = 2, to = length(x))){
s = s + (x[j] - median + C)
s = min(0, s)
if (s < threshold){
day_change = days[j]
day_index = j
weather_change_index[i] = day_index
break
}
}
plot(x = xp, y = x, xlab = 'Dates', ylab='Temperatures', main=c('Atlanta Temperatures in ', as.character(1995+i)))
points(x = xp[day_index], y= x[day_index], col = 'red', pch=19, cex = 2)
abline(h = median)
print(as.character(day_change))
}
[1] "21-Sep"

[1] "27-Sep"

[1] "5-Oct"

[1] "22-Sep"

[1] "8-Sep"

[1] "6-Sep"

[1] "3-Sep"

[1] "13-Sep"

[1] "21-Sep"

[1] "11-Jul"

[1] "18-Sep"

[1] "3-Jul"

[1] "21-Sep"

[1] "7-Jul"

[1] "3-Jul"

[1] "8-Sep"

[1] "4-Jul"

[1] "18-Aug"

[1] "24-Sep"

[1] "15-Sep"

The exponential smoothing is causing issues at the beggingin of a few years where the temperatures drop off tremendously in as early as July (2005, 2007, 2009, 2010 and 2012). This is because the trend at the beginning of these years are decreasing, so the exponential smoothing is amplifying this drop off. As an effect, this is causing an extremely early change detection within our CUSUM algorithm. Let’s examine 2012 and see what we can do
plot(temps_ts[17,], main = 'Atlanta Temperatures 2012')

plot(HoltWinters(temps_ts[17,], alpha = 0.2, beta = 0.2, gamma = FALSE))

The issue with the Holt-Winters filtering is pretty clear. Let’s try to smooth the data with a 7 day moving average, and then apply an exponential smoothing to try and fix this issue
moving_average = SMA(temps[17,], n=7)
plot(moving_average, main = '7 Day Moving Average for 2012 Temperatures in Atlanta')

holt = HoltWinters(moving_average[7:length(moving_average)], alpha = 0.2, beta = 0.2, gamma = FALSE)
plot(holt)

The moving average appears to have fixed the massive drop off at the begining of the month. Let’s apply CUSUM now to see the results for 2012
forecast <- holt$fitted[,1]
median = median(forecast)
s = forecast[1]
C = 0.2
threshold = -10
for(i in seq(from = 2, to = length(forecast))){
s = s + (forecast[i] - median + C)
s = min(0, s)
if (s < threshold){
day_change = days[i+6]
day_index = i
break
}
}
print(day_change)
[1] "18-Sep"
plot(x = xp[7:length(xp)], y = forecast, xlab = 'Dates', ylab='Temperatures', main='Temperatures in 2012 w/ Median Temperature and 7 Day Moving Avg')
points(x = xp[day_index+6], y= forecast[day_index], col = 'red',pch=19, cex = 2)
abline(h = median)

This is much better. Let’s try again and apply a 7 day moving average to all data before exponentially smoothing and applying a CUSUM algorithm. We will also be saving the index locations of the dates where summer officially ended to use to determine if the unofficial summer is getting later. That variable will be called “weather_change_index”
weather_change_index = rep(0, 20)
for (i in seq(1,20)){
moving_average = SMA(temps[i,], n=7)
temp_h <- HoltWinters(moving_average[7:length(moving_average)],alpha=0.2, beta = 0.2, gamma = FALSE)
x <- temp_h$fitted[,1]
median = median(x)
C = 1
threshold = -25
s = x[1] - median + C
for(j in seq(from = 2, to = length(x))){
s = s + (x[j] - median + C)
s = min(0, s)
if (s < threshold){
day_change = days[j+6]
day_index = j
weather_change_index[i] = day_index
break
}
}
plot(x = xp[7:length(xp)], y = x, xlab = 'Dates', ylab='Temperatures', main=c('Atlanta Temperatures in ', as.character(1995+i)))
points(x = xp[day_index+6], y= x[day_index], col = 'red', pch=19, cex = 2)
abline(h = median)
print(as.character(day_change))
}
[1] "23-Sep"

[1] "29-Sep"

[1] "3-Oct"

[1] "23-Sep"

[1] "10-Sep"

[1] "10-Sep"

[1] "26-Sep"

[1] "15-Sep"

[1] "22-Sep"

[1] "10-Oct"

[1] "21-Sep"

[1] "9-Oct"

[1] "25-Sep"

[1] "6-Oct"

[1] "6-Sep"

[1] "11-Sep"

[1] "26-Sep"

[1] "22-Aug"

[1] "26-Sep"

[1] "20-Sep"

It appears that our algorithm works very well with the exception of 2013. There was an outlier of a week for temperature in August where the temps dropped to nearly 75 degrees (moving average altered) before climbing to back over 90 degrees. It was hard to account for this in the cumsum algorithm. As such, the year will just be marked as an outlier for the algorithm. Let’s now use the weather_change_index to extract for each year, all the days before that index as summer, and count how many days there are. If the unofficial end of summer is getting later, then with increasing years, we should see more days of summer.
days_of_summer = rep(0,20)
for (i in seq(1,20)){
x = as.matrix(temps_ts[i,])
x = x[1:weather_change_index[i]]
days_of_summer[i] = length(x)
}
years = seq(1996, 2015)
data = c(years, days_of_summer)
plot(x = years, y = days_of_summer, xlab ='Years', ylab = 'Days of Summer', main = 'Days of Summer per Year')
abline(lm(formula = days_of_summer~years))

The outlier from 2013 appears to be dragging the regression down. Let’s remove that outlier and replot the regression line
years = 1996:2014
days_of_summer = days_of_summer[days_of_summer != 47]
plot(x = years, y = days_of_summer, xlab ='Years', ylab = 'Days of Summer', main = 'Days of Summer per Year')
abline(lm(formula = days_of_summer~years))

*Conclusion
It appears that the official end of summer is about consistent throughout the last 20 years. There is a little bit of a downards trend, but it wouldn’t be erroneous to interpret the trend line as flat. Notice how the days of summer per year are pretty random as well.
LS0tCnRpdGxlOiAiSFc0IC0gS2VsbHkgXCJTY290dFwiIFNpbXMiCm91dHB1dDogcGRmX2RvY3VtZW50CnBkZl9kb2N1bWVudDogZGVmYXVsdApodG1sX25vdGVib29rOiBkZWZhdWx0Ci0tLQoKKio3LjEqKgotLS0tLS0tLS0tLS0tLS0tLS0tCkRlc2NyaWJlIGEgc2l0dWF0aW9uIG9yIHByb2JsZW0gZnJvbSB5b3VyIGpvYiwgZXZlcnlkYXkgbGlmZSwgY3VycmVudCBldmVudHMsIGV0Yy4sIGZvciB3aGljaCBleHBvbmVudGlhbApzbW9vdGhpbmcgd291bGQgYmUgYXBwcm9wcmlhdGUuIFdoYXQgZGF0YSB3b3VsZCB5b3UgbmVlZD8gV291bGQgeW91IGV4cGVjdCB0aGUgdmFsdWUgb2YgKHRoZQpmaXJzdCBzbW9vdGhpbmcgcGFyYW1ldGVyKSB0byBiZSBjbG9zZXIgdG8gMCBvciAxLCBhbmQgd2h5PwoKPldpdGggaG9tZSBhdXRvbWF0aW9uIGF0IGFsbCB0aW1lIGhpZ2hzLCBldmVyeW9uZSBpcyB0dXJuaW5nIHRvIGF1dG9tYXRlZCBjZW50cmFsIGFpciB0byBrZWVwIHRoZWlyIGhvdXNlIGF0IHRoZSBkZXNpcmVkIGNsaW1hdGUgd2hpbGUgYmVpbmcgZW5lcmd5IGVmZmljaWVuY3kuIFRha2UgYSBuZXN0IGZvciBleGFtcGxlLiBZb3UgcHJvZ3JhbSB0aGUgZGVzaXJlZCB0ZW1wZXJhdHVyZXMgYXQgY2VydGFpbiB0aW1lcyBvZiB0aGUgZGF5LiBZb3UgbWlnaHQgaGF2ZSB5b3VyIGFpciB0dXJuZWQgb2ZmIGR1cmluZyB0aGUgZWFybHkgbW9ybmluZyBob3VycyB3aGVuIHRoZSBzdW4gaXMganVzdCByaXNpbmcgYW5kIGl0IGlzIHN0aWxsIHJlbGF0aXZlbHkgY29vbC4gQnV0IGJ5IE1pZCB0byBsYXRlIGFmdGVybm9vbiwgeW91IG1pZ2h0IGhhdmUgaXQgcHJvZ3JhbW1lZCB0byB0dXJuIG9uIGFuZCBrZWVwIHlvdXIgaG91c2UgY29vbC4gVGhlIG5lc3QgdGhlcm1vc3RhdCBiYXNpY2FsbHkgbW9uaXRvcnMgdGhlIGFtYmllbnQgdGVtcGVyYXR1cmUsIGFuZCB3aGVuIGl0IHN1ZmZpY2llbnRseSByaXNlcyBhYm92ZSBvciBkcm9wcyBiZWxvdyB0aGUgZGVzaXJlZCB0ZW1wZXJhdHVyZSwgaXQgZWl0aGVyIHNodXRzIG9mZiBvciB0dXJucyBvbiwgZGVwZW5kaW5nIG9uIHRoZSBzaXR1YXRpb24uIExldCdzIHNheSBmb3IgaW5zdGFuY2UgeW91IGhhdmUgaXQgc2V0IGZvciA3MCBkZWdyZWVzIEZhaHJlbmhlaXQgYXMgdGhlIGRlc2lyZWQgdGVtcGVyYXR1cmUsIGlmIHNvbWVvbmUgaXMgY29uc3RhbnRseSBydW5uaW5nIGluIG9yIG91dCBvZiB0aGUgaG91c2UsIGhhcyBhIHdpbmRvdyBvcGVuLCBhIGNlaWxpbmcgZmFuLCBldGMsIHRoZSB0ZW1wZXJhdHVyZSBtaWdodCBmbHVjdHVhdGUgYWxvdCBhcm91bmQgdGhhdCA3MCBkZWdyZWUgbWFyay4gSWYgdGhlIG5lc3QgdHVybmVkIG9uIGF0IDcwLjUgb3IgYWJvdmUsIGFuZCB0dXJuZWQgb2ZmIGF0IDY5LjUgb3IgbGVzcywgdGhlbiB5b3VyIGNlbnRyYWwgYWlyIHdvdWxkIGNvbnN0YW50bHkgYmUgdHVybmluZyBvZmYgYW5kIG9uIGFuZCB3b3VsZG4ndCBiZSB2ZXJ5IGVmZmVjaWVudC4gVGhlcmVmb3JlLCBhbiBleHBvbmV0aWFsIHNtb290aGluZyB0cmFuc2Zvcm1hdGlvbiBvZiB0aGUgYW1iaWVudCB0ZW1wZXJhdHVyZSB3b3VsZCBiZSBhcHByb3ByaWF0ZSBoZXJlIHRvIHByZXZlbnQgdGhlIGFpciBmcm9tIHR1cm5pbmcgb24ganVzdCBiZWNhdXNlIHNvbWVvbmUgb3BlbmVkIHRoZSBkb29yIGFuZCBlbnRlcmVkIHRoZSBob3VzZS4gSSdkIGltYWdpbmUgdGhlIGFscGhhIHZhbHVlIHdvdWxkIGJlIGNsb3NlciAwLCBtZWFuaW5nIHRoZSBwcmV2aW91cyB0ZW1wZXJhdHVyZSBoYXMgbW9yZSB3ZWlnaHQgb3ZlciB0aGUgY3VycmVudCB0ZW1wZXJhdHVyZS4gVGhpcyBpcyBiZWNhdXNlLCBpbiB0aG9zZSBpbnN0YW5jZXMgdGhhdCBzb21lb25lIG9wZW5zIHRoZSBkb29yIG9yIGFueSBvZiB0aGUgb3RoZXIgYWZvcmVtZW50aW9uZWQgc3RpbXVsaSwgaXQgd291bGQgY2F1c2UgYSBtb21lbnRhcnkgc3Bpa2UgaW4gcmVhZGluZ3MsIGFuZCB0aGVuIHJlLXN0YWJpbGl6ZS4gQnkgZ2l2aW5nIG1vcmUgd2VpZ2h0IHRvIHBhc3QgcmVhZGluZ3MgdGhhdCBhcmUgbW9yZSBjb25zaXN0ZW50LCB0aGlzIHdvdWxkIHByb3Blcmx5IHNtb290aCB0aGUgdGVtcGVyYXR1cmUgcmVhZGluZ3MgdG8gdGhvc2UgdGhhdCB3ZXJlIG1vcmUgY29uc2lzdGVudCB3aXRoIG9uZSBhbm90aGVyLgoKCioqUXVlc3Rpb24gNy4yKioKLS0tLS0tLS0tLS0tLS0tLS0KVXNpbmcgdGhlIDIwIHllYXJzIG9mIGRhaWx5IGhpZ2ggdGVtcGVyYXR1cmUgZGF0YSBmb3IgQXRsYW50YSAoSnVseSB0aHJvdWdoIE9jdG9iZXIpIGZyb20gUXVlc3Rpb24gNi4yCihmaWxlIHRlbXBzLnR4dCksIGJ1aWxkIGFuZCB1c2UgYW4gZXhwb25lbnRpYWwgc21vb3RoaW5nIG1vZGVsIHRvIGhlbHAgbWFrZSBhIGp1ZGdtZW50IG9mIHdoZXRoZXIKdGhlIHVub2ZmaWNpYWwgZW5kIG9mIHN1bW1lciBoYXMgZ290dGVuIGxhdGVyIG92ZXIgdGhlIDIwIHllYXJzLiAoUGFydCBvZiB0aGUgcG9pbnQgb2YgdGhpcyBhc3NpZ25tZW50IGlzCmZvciB5b3UgdG8gdGhpbmsgYWJvdXQgaG93IHlvdSBtaWdodCB1c2UgZXhwb25lbnRpYWwgc21vb3RoaW5nIHRvIGFuc3dlciB0aGlzIHF1ZXN0aW9uLiBGZWVsIGZyZWUgdG8KY29tYmluZSBpdCB3aXRoIG90aGVyIG1vZGVscyBpZiB5b3XigJlkIGxpa2UgdG8uIFRoZXJl4oCZcyBjZXJ0YWlubHkgbW9yZSB0aGFuIG9uZSByZWFzb25hYmxlIGFwcHJvYWNoLikKTm90ZTogaW4gUiwgeW91IGNhbiB1c2UgZWl0aGVyIEhvbHRXaW50ZXJzIChzaW1wbGVyIHRvIHVzZSkgb3IgdGhlIHNtb290aCBwYWNrYWdl4oCZcyBlcyBmdW5jdGlvbgooaGFyZGVyIHRvIHVzZSwgYnV0IG1vcmUgZ2VuZXJhbCkuIElmIHlvdSB1c2UgZXMsIHRoZSBIb2x0LVdpbnRlcnMgbW9kZWwgdXNlcyBtb2RlbD3igJ1BQU3igJ0gaW4gdGhlCmZ1bmN0aW9uIGNhbGwgKHRoZSBmaXJzdCBhbmQgc2Vjb25kIGNvbnN0YW50cyBhcmUgdXNlZCDigJxB4oCdZGRpdGl2ZWx5LCBhbmQgdGhlIHRoaXJkIChzZWFzb25hbGl0eSkgaXMgdXNlZArigJxN4oCddWx0aXBsaWNhdGl2ZWx5OyB0aGUgZG9jdW1lbnRhdGlvbiBkb2VzbuKAmXQgbWFrZSB0aGF0IGNsZWFyKS4gCgoKCgo+V2hpbGUgdHJ5aW5nIHRvIGV4cG9uZW50aWFsbHkgc21vb3RoIHRoZSBkYXRhLCB3ZSB3aWxsIG5lZWQgdG8gZmlyc3QgZ2V0IGFuIGlkZWEgb2YgYW4gb3B0aW1hbCBhbHBoYSBhbmQgYmV0YSBwYXJhbWV0ZXIgZm9yIHRoZSBIb2x0V2ludGVycyBmdW5jdGlvbi4gTGV0J3MgcGxvdCB0aGUgZGF0YSBmb3IgMTk5NiBhbmQgZXhwZXJpbWVudCB3aXRoIGV2ZXJ5IGNvbWJpbmF0aW9uIG9mIGFscGhhIGZyb20gMC4yIHRvIDAuNSBhbmQgYmV0YSBmcm9tIDAuMCB0byAwLjUKCmBgYHtyfQpsaWJyYXJ5KFRUUikKdGVtcHMgPC0gcmVhZC50YWJsZSgndGVtcHMudHh0JywgaGVhZGVyID0gVFJVRSwgc3RyaW5nc0FzRmFjdG9ycyA9IEZBTFNFKQojdGVtcHMkREFZIDwtIGZvcm1hdChhcy5EYXRlKHRlbXBzJERBWSwgZm9ybWF0ID0gJyVkLSViJyksICclZC0lYicpCmRheXMgPC0gdGVtcHMkREFZCnRlbXBzIDwtIHQodGVtcHNbLDI6bmNvbCh0ZW1wcyldKQpjb2xuYW1lcyh0ZW1wcykgPC0gZGF5cwpyb3duYW1lcyh0ZW1wcykgPC0gMTk5NjoyMDE1CnRlbXBzX3RzIDwtIHRzKHRlbXBzLCBzdGFydCA9IDE5OTYsIGZyZXF1ZW5jeT0xKQoKZm9yKGkgaW4gc2VxKGZyb20gPSAwLjIsIHRvID0gMC41LCBieSA9IDAuMSkpewogIGZvcihqIGluIHNlcShmcm9tID0gMC4wMCwgdG8gPSAwLjUsIGJ5ID0gMC4xKSl7CiAgICAgIGNhdCgnQWxwaGE6ICcsaSwgJ0JldGE6ICcsIGosJ1xuJykKICAgICAgdGVtcF9oIDwtIEhvbHRXaW50ZXJzKHRlbXBzX3RzWzEsXSxhbHBoYT1pLCBiZXRhID0gaiwgZ2FtbWEgPSBGQUxTRSkKICAgICAgcGxvdCh0ZW1wX2gpCn0KfQpgYGAKCj4gQW4gYWxwaGEgdmFsdWUgb2YgMC4yIGFuZCBiZXRhIG9mIDAuMiBzZWVtcyB0byBiZXN0IHNtb290aCB0aGUgZGF0YSB3aXRob3V0IGxvc2luZyBhbnkgbWFqb3IgY2hhcmFjdGVyc3RpYyBjaGFuZ2VzLiBJdCBhbHNvIGRvZXNuJ3QgYXBwZWFyIHRvIGFtcGxpZnkgYW55IGNoYXJhY3RlcmlzdGljIGNoYW5nZXMuIExldCdzIEF0dGVtcHQgYSBDVU1TVU0gYWxnb3JpdGhtIG9uIHRoZSAxOTk2IGRhdGEgd2l0aCBhIDAuMiBhbHBoYSBhbmQgYmV0YS4KCgpgYGB7cn0KdGVtcF9oIDwtIEhvbHRXaW50ZXJzKHRlbXBzX3RzWzEsXSxhbHBoYT0wLjIsIGJldGEgPSAwLjIsIGdhbW1hID0gRkFMU0UpCmZvcmVjYXN0IDwtIHRlbXBfaCRmaXR0ZWRbLDFdCgphdmcgPSBtZWFuKGZvcmVjYXN0KQpzID0gZm9yZWNhc3RbMV0KQyA9IDEKdGhyZXNob2xkID0gLTMwCmZvcihpIGluIHNlcShmcm9tID0gMiwgdG8gPSBsZW5ndGgoZm9yZWNhc3QpKSl7CiAgcyA9IHMgKyAoZm9yZWNhc3RbaV0gLSBhdmcgKyBDKQogIAogIHMgPSBtaW4oMCwgcykKICAKICBpZiAocyA8IHRocmVzaG9sZCl7CiAgICBkYXlfY2hhbmdlID0gZGF5c1tpXQogICAgZGF5X2luZGV4ID0gaQogICAgYnJlYWsKICB9CiAgCiAgCn0KcHJpbnQoZGF5X2NoYW5nZSkKCgoKeHAgPSBhcy5EYXRlKHN0cnB0aW1lKGRheXMsIGZvcm1hdCA9ICclZC0lYicpKQptYXggPSBsZW5ndGgoeHApIC0gMQp4cCA9IHhwWzI6bWF4XQpwbG90KHggPSB4cCwgeSA9IGZvcmVjYXN0LCB4bGFiID0gJ0RhdGVzJywgeWxhYj0nVGVtcGVyYXR1cmVzJywgbWFpbj0nQXRsYW50YSBUZW1wZXJhdHVyZXMgaW4gMTk5NicpCnBvaW50cyh4ID0geHBbZGF5X2luZGV4XSwgeT0gZm9yZWNhc3RbZGF5X2luZGV4XSwgY29sID0gJ3JlZCcpCmFibGluZShoID0gYXZnKQpgYGAKCj4gVGhlIHNtb290aGluZyBhcHBlYXJzIHRvIGhhdmUgaGVscGVkIGNoYXJhY3Rlcml6ZSB0aGUgZXZlbnQgY2hhbmdlIG9mIHN1bW1lciB0byBmYWxsIGF0IFNlcHQgMjl0aC4gQmVmb3JlIHRoYXQgZGF0ZSwgdGhlIHRlbXBlcmF0dXJlIGRpZCBzcGlrZSB1cCB0byBqdXN0IGJlbG93IHRoZSBhdmVyYWdlIHRlbXBlcmF0dXJlLCBidXQgbmV2ZXIgcXVpdGUgbWFkZSBpdCBwYXN0LiBJdCB0aGVuIGZlbGwgYmFjayBkb3duIHRvIHdoaWNoIGl0IG5ldmVyIHJldHVybmVkIGhpZ2hlciB0aGFuIHRoZSBhdmVyYWdlIHRlbXBlcmF0dXJlLiBBcyBhIHF1YWxpdHkgY2hlY2ssIGxldCdzIHNlZSBpZiB0aGUgYXZlcmFnZSB0ZW1wZXJhdHVyZSBpcyB0aGUgcmlnaHQgdmFsdWUgdG8gdXNlLiBJZiB0aGUgZGF0YSBoYXMgYSBsb3Qgb2Ygb3V0bGllcnMgb3IgaXMgZ3JlYXRseSBza2V3ZWQgbGVmdCBvciByaWdodCwgdGhlbiB0aGlzIHdpbGwgZXJyb25lb3VzbHkgcHVsbCB0aGUgbWVhbiBhd2F5IGZyb20gdGhlIHRydWUgY2VudGVyIG9mIHRoYXQgZGF0YS4gSWYgdGhhdCBpcyB0aGUgY2FzZSwgdGhlbiB0aGUgbWVkaWFuIHRlbXBlcmF0dXJlIG9mIHRoZSBkYXRhIGlzIHRoZSBtb3JlIGFwcHJvcHJpYXRlIG1ldHJpYyB0byB1c2UKCmBgYHtyfQpoaXN0KHRlbXBzX3RzWzEsXSwgbWFpbiA9ICcxOTk2IEF0bGFudGEgVGVtcGVyYXR1cmVzJywgeGxhYiA9ICdUZW1wcycpCmBgYAoKPiBUaGUgZGF0YSBpcyBncmVhdGx5IGxlZnQgc2tld2VkLiBMZXQncyByZXJ1biB0aGUgYW5hbHlzaXMgYWdhaW4sIGJ1dCB1c2luZyB0aGUgbWVkaWFuIGluc3RlYWQgb2YgdGhlIG1lYW4gaW4gdGhlIENVU1VNIGFsZ29yaXRobQoKYGBge3J9CnRlbXBfaCA8LSBIb2x0V2ludGVycyh0ZW1wc190c1sxLF0sYWxwaGE9MC4yLCBiZXRhID0gMC4yLCBnYW1tYSA9IEZBTFNFKQpmb3JlY2FzdCA8LSB0ZW1wX2gkZml0dGVkWywxXQoKbWVkaWFuID0gbWVkaWFuKGZvcmVjYXN0KQpzID0gZm9yZWNhc3RbMV0KQyA9IDEKdGhyZXNob2xkID0gLTMwCmZvcihpIGluIHNlcShmcm9tID0gMiwgdG8gPSBsZW5ndGgoZm9yZWNhc3QpKSl7CiAgcyA9IHMgKyAoZm9yZWNhc3RbaV0gLSBtZWRpYW4gKyBDKQogIAogIHMgPSBtaW4oMCwgcykKICAKICBpZiAocyA8IHRocmVzaG9sZCl7CiAgICBkYXlfY2hhbmdlID0gZGF5c1tpXQogICAgZGF5X2luZGV4ID0gaQogICAgYnJlYWsKICB9CiAgCiAgCn0KcHJpbnQoZGF5X2NoYW5nZSkKCgoKCnBsb3QoeCA9IHhwLCB5ID0gZm9yZWNhc3QsIHhsYWIgPSAnRGF0ZXMnLCB5bGFiPSdUZW1wZXJhdHVyZXMnLCBtYWluPSdBdGxhbnRhIFRlbXBlcmF0dXJlcyBpbiAxOTk2IFVzaW5nIE1lZGlhbiBUZW1wZXJhdHVyZScpCnBvaW50cyh4ID0geHBbZGF5X2luZGV4XSwgeT0gZm9yZWNhc3RbZGF5X2luZGV4XSwgY29sID0gJ3JlZCcpCmFibGluZShoID0gbWVkaWFuKQpgYGAKCj4gT25lIGNhbiBhcmd1ZSB0aGF0IHRoZSBtZWRpYW4gd2FzIGEgYmV0dGVyIG1ldHJpYyB0byB1c2UuIFRoZSBDVU1TVU0gZm91bmQgdGhlIGFwcHJvcHJpYXRlIHBvaW50IGF0IHdoaWNoIHRoZSBldmVudCBjaGFuZ2UgZHJvcHBlZCBiZWxvdyB0aGUgZGF0YSdzIG1lZGlhbiB2YWx1ZSBzb29uZXIgdGhhbiB0aGUgbWVhbiBtZXRyaWMgZGlkLiBBbHRob3VnaCB0aGUgdGVtcGVyYXR1cmUgc2xpZ2h0bHkgaW5jcmVhc2VkIGZyb20gdGhhdCBwb2ludCwgaXQgbmV2ZXIgY3Jvc3NlZCB0aGUgbWVkaWFuIGxpbmUgYWdhaW4gZm9yIHRoZSByZXN0IG9mIHRoZSB5ZWFyLiBMZXQncyB1c2UgdGhpcyBhbmFseXNpcyB0byBndWlkZSB0aGUgcmVzdCBvZiBvdXIgaW52ZXN0aWdhdGlvbiBvbiB0aGUgcmVtYWluaW5nIHllYXJzIG9mIGRhdGEuCgoKCgpgYGB7cn0Kd2VhdGhlcl9jaGFuZ2VfaW5kZXggPSByZXAoMCwgMjApCgpmb3IgKGkgaW4gc2VxKDEsMjApKXsKICAKICB0ZW1wX2ggPC0gSG9sdFdpbnRlcnModGVtcHNfdHNbaSxdLGFscGhhPTAuMiwgYmV0YSA9IDAuMiwgZ2FtbWEgPSBGQUxTRSkKICB4IDwtIHRlbXBfaCRmaXR0ZWRbLDFdCiAgbWVkaWFuID0gbWVkaWFuKHgpCiAgQyA9IDEKICB0aHJlc2hvbGQgPSAtMzAKICBzID0geFsxXSAtIG1lZGlhbiArIEMKCiAgCiAgZm9yKGogaW4gc2VxKGZyb20gPSAyLCB0byA9IGxlbmd0aCh4KSkpewogICAgcyA9IHMgKyAoeFtqXSAtIG1lZGlhbiArIEMpCiAgICBzID0gbWluKDAsIHMpCgoKICAgIGlmIChzIDwgdGhyZXNob2xkKXsKICAgICAgZGF5X2NoYW5nZSA9IGRheXNbal0KICAgICAgZGF5X2luZGV4ID0gagogICAgICB3ZWF0aGVyX2NoYW5nZV9pbmRleFtpXSA9IGRheV9pbmRleAogICAgICBicmVhawogICAgfQogIAogIAogIH0KICAKICBwbG90KHggPSB4cCwgeSA9IHgsIHhsYWIgPSAnRGF0ZXMnLCB5bGFiPSdUZW1wZXJhdHVyZXMnLCBtYWluPWMoJ0F0bGFudGEgVGVtcGVyYXR1cmVzIGluICcsIGFzLmNoYXJhY3RlcigxOTk1K2kpKSkKICBwb2ludHMoeCA9IHhwW2RheV9pbmRleF0sIHk9IHhbZGF5X2luZGV4XSwgY29sID0gJ3JlZCcsIHBjaD0xOSwgY2V4ID0gMikKICBhYmxpbmUoaCA9IG1lZGlhbikKICBwcmludChhcy5jaGFyYWN0ZXIoZGF5X2NoYW5nZSkpCiAgCn0KYGBgCgo+IFRoZSBleHBvbmVudGlhbCBzbW9vdGhpbmcgaXMgY2F1c2luZyBpc3N1ZXMgYXQgdGhlIGJlZ2dpbmdpbiBvZiBhIGZldyB5ZWFycyB3aGVyZSB0aGUgdGVtcGVyYXR1cmVzIGRyb3Agb2ZmIHRyZW1lbmRvdXNseSBpbiBhcyBlYXJseSBhcyBKdWx5ICgyMDA1LCAyMDA3LCAyMDA5LCAyMDEwIGFuZCAyMDEyKS4gVGhpcyBpcyBiZWNhdXNlIHRoZSB0cmVuZCBhdCB0aGUgYmVnaW5uaW5nIG9mIHRoZXNlIHllYXJzIGFyZSBkZWNyZWFzaW5nLCBzbyB0aGUgZXhwb25lbnRpYWwgc21vb3RoaW5nIGlzIGFtcGxpZnlpbmcgdGhpcyBkcm9wIG9mZi4gQXMgYW4gZWZmZWN0LCB0aGlzIGlzIGNhdXNpbmcgYW4gZXh0cmVtZWx5IGVhcmx5IGNoYW5nZSBkZXRlY3Rpb24gd2l0aGluIG91ciBDVVNVTSBhbGdvcml0aG0uIExldCdzIGV4YW1pbmUgMjAxMiBhbmQgc2VlIHdoYXQgd2UgY2FuIGRvCgpgYGB7cn0KcGxvdCh0ZW1wc190c1sxNyxdLCBtYWluID0gJ0F0bGFudGEgVGVtcGVyYXR1cmVzIDIwMTInKQpwbG90KEhvbHRXaW50ZXJzKHRlbXBzX3RzWzE3LF0sIGFscGhhID0gMC4yLCBiZXRhID0gMC4yLCBnYW1tYSA9IEZBTFNFKSkKCmBgYAoKPiBUaGUgaXNzdWUgd2l0aCB0aGUgSG9sdC1XaW50ZXJzIGZpbHRlcmluZyBpcyBwcmV0dHkgY2xlYXIuIExldCdzIHRyeSB0byBzbW9vdGggdGhlIGRhdGEgd2l0aCBhIDcgZGF5IG1vdmluZyBhdmVyYWdlLCBhbmQgdGhlbiBhcHBseSBhbiBleHBvbmVudGlhbCBzbW9vdGhpbmcgdG8gdHJ5IGFuZCBmaXggdGhpcyBpc3N1ZQoKCmBgYHtyfQptb3ZpbmdfYXZlcmFnZSA9IFNNQSh0ZW1wc1sxNyxdLCBuPTcpCnBsb3QobW92aW5nX2F2ZXJhZ2UsIG1haW4gPSAnNyBEYXkgTW92aW5nIEF2ZXJhZ2UgZm9yIDIwMTIgVGVtcGVyYXR1cmVzIGluIEF0bGFudGEnKQoKaG9sdCA9IEhvbHRXaW50ZXJzKG1vdmluZ19hdmVyYWdlWzc6bGVuZ3RoKG1vdmluZ19hdmVyYWdlKV0sIGFscGhhID0gMC4yLCBiZXRhID0gMC4yLCBnYW1tYSA9IEZBTFNFKQpwbG90KGhvbHQpCgoKYGBgCgo+IFRoZSBtb3ZpbmcgYXZlcmFnZSBhcHBlYXJzIHRvIGhhdmUgZml4ZWQgdGhlIG1hc3NpdmUgZHJvcCBvZmYgYXQgdGhlIGJlZ2luaW5nIG9mIHRoZSBtb250aC4gTGV0J3MgYXBwbHkgQ1VTVU0gbm93IHRvIHNlZSB0aGUgcmVzdWx0cyBmb3IgMjAxMgoKYGBge3J9CmZvcmVjYXN0IDwtIGhvbHQkZml0dGVkWywxXQoKbWVkaWFuID0gbWVkaWFuKGZvcmVjYXN0KQpzID0gZm9yZWNhc3RbMV0KQyA9IDAuMgp0aHJlc2hvbGQgPSAtMTAKZm9yKGkgaW4gc2VxKGZyb20gPSAyLCB0byA9IGxlbmd0aChmb3JlY2FzdCkpKXsKICBzID0gcyArIChmb3JlY2FzdFtpXSAtIG1lZGlhbiArIEMpCiAgCiAgcyA9IG1pbigwLCBzKQoKICBpZiAocyA8IHRocmVzaG9sZCl7CiAgICBkYXlfY2hhbmdlID0gZGF5c1tpKzZdCiAgICBkYXlfaW5kZXggPSBpCiAgICBicmVhawogIH0KICAKfQpwcmludChkYXlfY2hhbmdlKQoKcGxvdCh4ID0geHBbNzpsZW5ndGgoeHApXSwgeSA9IGZvcmVjYXN0LCB4bGFiID0gJ0RhdGVzJywgeWxhYj0nVGVtcGVyYXR1cmVzJywgbWFpbj0nVGVtcGVyYXR1cmVzIGluIDIwMTIgdy8gTWVkaWFuIFRlbXBlcmF0dXJlIGFuZCA3IERheSBNb3ZpbmcgQXZnJykKcG9pbnRzKHggPSB4cFtkYXlfaW5kZXgrNl0sIHk9IGZvcmVjYXN0W2RheV9pbmRleF0sIGNvbCA9ICdyZWQnLHBjaD0xOSwgY2V4ID0gMikKYWJsaW5lKGggPSBtZWRpYW4pCmBgYAoKPiBUaGlzIGlzIG11Y2ggYmV0dGVyLiBMZXQncyB0cnkgYWdhaW4gYW5kIGFwcGx5IGEgNyBkYXkgbW92aW5nIGF2ZXJhZ2UgdG8gYWxsIGRhdGEgYmVmb3JlIGV4cG9uZW50aWFsbHkgc21vb3RoaW5nIGFuZCBhcHBseWluZyBhIENVU1VNIGFsZ29yaXRobS4gV2Ugd2lsbCBhbHNvIGJlIHNhdmluZyB0aGUgaW5kZXggbG9jYXRpb25zIG9mIHRoZSBkYXRlcyB3aGVyZSBzdW1tZXIgb2ZmaWNpYWxseSBlbmRlZCB0byB1c2UgdG8gZGV0ZXJtaW5lIGlmIHRoZSB1bm9mZmljaWFsIHN1bW1lciBpcyBnZXR0aW5nIGxhdGVyLiBUaGF0IHZhcmlhYmxlIHdpbGwgYmUgY2FsbGVkICJ3ZWF0aGVyX2NoYW5nZV9pbmRleCIKCgoKYGBge3J9CndlYXRoZXJfY2hhbmdlX2luZGV4ID0gcmVwKDAsIDIwKQpmb3IgKGkgaW4gc2VxKDEsMjApKXsKICBtb3ZpbmdfYXZlcmFnZSA9IFNNQSh0ZW1wc1tpLF0sIG49NykKICB0ZW1wX2ggPC0gSG9sdFdpbnRlcnMobW92aW5nX2F2ZXJhZ2VbNzpsZW5ndGgobW92aW5nX2F2ZXJhZ2UpXSxhbHBoYT0wLjIsIGJldGEgPSAwLjIsIGdhbW1hID0gRkFMU0UpCiAgeCA8LSB0ZW1wX2gkZml0dGVkWywxXQogIG1lZGlhbiA9IG1lZGlhbih4KQogIEMgPSAxCiAgdGhyZXNob2xkID0gLTI1CiAgcyA9IHhbMV0gLSBtZWRpYW4gKyBDCgogIAogIGZvcihqIGluIHNlcShmcm9tID0gMiwgdG8gPSBsZW5ndGgoeCkpKXsKICAgIHMgPSBzICsgKHhbal0gLSBtZWRpYW4gKyBDKQogICAgcyA9IG1pbigwLCBzKQoKCiAgICBpZiAocyA8IHRocmVzaG9sZCl7CiAgICAgIGRheV9jaGFuZ2UgPSBkYXlzW2orNl0KICAgICAgZGF5X2luZGV4ID0gagogICAgICB3ZWF0aGVyX2NoYW5nZV9pbmRleFtpXSA9IGRheV9pbmRleAogICAgICBicmVhawogICAgfQogIAogIAogIH0KCiAgcGxvdCh4ID0geHBbNzpsZW5ndGgoeHApXSwgeSA9IHgsIHhsYWIgPSAnRGF0ZXMnLCB5bGFiPSdUZW1wZXJhdHVyZXMnLCBtYWluPWMoJ0F0bGFudGEgVGVtcGVyYXR1cmVzIGluICcsIGFzLmNoYXJhY3RlcigxOTk1K2kpKSkKICBwb2ludHMoeCA9IHhwW2RheV9pbmRleCs2XSwgeT0geFtkYXlfaW5kZXhdLCBjb2wgPSAncmVkJywgcGNoPTE5LCBjZXggPSAyKQogIGFibGluZShoID0gbWVkaWFuKQogIHByaW50KGFzLmNoYXJhY3RlcihkYXlfY2hhbmdlKSkKICAKfQpgYGAKCj4gSXQgYXBwZWFycyB0aGF0IG91ciBhbGdvcml0aG0gd29ya3MgdmVyeSB3ZWxsIHdpdGggdGhlIGV4Y2VwdGlvbiBvZiAyMDEzLiBUaGVyZSB3YXMgYW4gb3V0bGllciBvZiBhIHdlZWsgZm9yIHRlbXBlcmF0dXJlIGluIEF1Z3VzdCB3aGVyZSB0aGUgdGVtcHMgZHJvcHBlZCB0byBuZWFybHkgNzUgZGVncmVlcyAobW92aW5nIGF2ZXJhZ2UgYWx0ZXJlZCkgYmVmb3JlIGNsaW1iaW5nIHRvIGJhY2sgb3ZlciA5MCBkZWdyZWVzLiBJdCB3YXMgaGFyZCB0byBhY2NvdW50IGZvciB0aGlzIGluIHRoZSBjdW1zdW0gYWxnb3JpdGhtLiBBcyBzdWNoLCB0aGUgeWVhciB3aWxsIGp1c3QgYmUgbWFya2VkIGFzIGFuIG91dGxpZXIgZm9yIHRoZSBhbGdvcml0aG0uIExldCdzIG5vdyB1c2UgdGhlIHdlYXRoZXJfY2hhbmdlX2luZGV4IHRvIGV4dHJhY3QgZm9yIGVhY2ggeWVhciwgYWxsIHRoZSBkYXlzIGJlZm9yZSB0aGF0IGluZGV4IGFzIHN1bW1lciwgYW5kIGNvdW50IGhvdyBtYW55IGRheXMgdGhlcmUgYXJlLiBJZiB0aGUgdW5vZmZpY2lhbCBlbmQgb2Ygc3VtbWVyIGlzIGdldHRpbmcgbGF0ZXIsIHRoZW4gd2l0aCBpbmNyZWFzaW5nIHllYXJzLCB3ZSBzaG91bGQgc2VlIG1vcmUgZGF5cyBvZiBzdW1tZXIuCgoKYGBge3J9CmRheXNfb2Zfc3VtbWVyID0gcmVwKDAsMjApCmZvciAoaSBpbiBzZXEoMSwyMCkpewogIHggPSBhcy5tYXRyaXgodGVtcHNfdHNbaSxdKQogIHggPSB4WzE6d2VhdGhlcl9jaGFuZ2VfaW5kZXhbaV1dCiAgZGF5c19vZl9zdW1tZXJbaV0gPSBsZW5ndGgoeCkKICAKfQoKCnllYXJzID0gc2VxKDE5OTYsIDIwMTUpCmRhdGEgPSBjKHllYXJzLCBkYXlzX29mX3N1bW1lcikKCnBsb3QoeCA9IHllYXJzLCB5ID0gZGF5c19vZl9zdW1tZXIsIHhsYWIgPSdZZWFycycsIHlsYWIgPSAnRGF5cyBvZiBTdW1tZXInLCBtYWluID0gJ0RheXMgb2YgU3VtbWVyIHBlciBZZWFyJykKYWJsaW5lKGxtKGZvcm11bGEgPSBkYXlzX29mX3N1bW1lcn55ZWFycykpCmBgYAoKPiBUaGUgb3V0bGllciBmcm9tIDIwMTMgYXBwZWFycyB0byBiZSBkcmFnZ2luZyB0aGUgcmVncmVzc2lvbiBkb3duLiBMZXQncyByZW1vdmUgdGhhdCBvdXRsaWVyIGFuZCByZXBsb3QgdGhlIHJlZ3Jlc3Npb24gbGluZQoKYGBge3J9CnllYXJzID0gMTk5NjoyMDE0CmRheXNfb2Zfc3VtbWVyID0gZGF5c19vZl9zdW1tZXJbZGF5c19vZl9zdW1tZXIgIT0gNDddCnBsb3QoeCA9IHllYXJzLCB5ID0gZGF5c19vZl9zdW1tZXIsIHhsYWIgPSdZZWFycycsIHlsYWIgPSAnRGF5cyBvZiBTdW1tZXInLCBtYWluID0gJ0RheXMgb2YgU3VtbWVyIHBlciBZZWFyJykKYWJsaW5lKGxtKGZvcm11bGEgPSBkYXlzX29mX3N1bW1lcn55ZWFycykpCmBgYAoKKioqQ29uY2x1c2lvbioqCgo+SXQgYXBwZWFycyB0aGF0IHRoZSBvZmZpY2lhbCBlbmQgb2Ygc3VtbWVyIGlzIGFib3V0IGNvbnNpc3RlbnQgdGhyb3VnaG91dCB0aGUgbGFzdCAyMCB5ZWFycy4gVGhlcmUgaXMgYSBsaXR0bGUgYml0IG9mIGEgZG93bmFyZHMgdHJlbmQsIGJ1dCBpdCB3b3VsZG4ndCBiZSBlcnJvbmVvdXMgdG8gaW50ZXJwcmV0IHRoZSB0cmVuZCBsaW5lIGFzIGZsYXQuIE5vdGljZSBob3cgdGhlIGRheXMgb2Ygc3VtbWVyIHBlciB5ZWFyIGFyZSBwcmV0dHkgcmFuZG9tIGFzIHdlbGwuIA==